import java.util.Iterator;
import java.util.LinkedList;

/**
 * TCSS343, Dr. Chinn, HW6B, 12/3/2011
 * Dijkstra's Algorithm
 * @author James Gunter
 * @author Justin Kudlo
 * @author Ryan Erickson
 */

/**
 * Class used to find the shortest path from one vertex to another vertex
 * using Dijkstra's Algorithm
 */
public class ShortestPath {
	
	
	LinkedList<Vertex> path;
	Double distance;
	
	/**
	 * Function used to traverse the user supplied graph, starting from the user 
	 * supplied source vertex, and ending at the user supplied destination 
	 * vertex. 
	 * 1.) Look for the source vertex and assign a weight of 0
	 * 2.) Take all the vertex and assign to a node and add to a binary heap.
	 * 3.) Pull out each node, iterate through each of its edges while 
	 * relabling each node* if the label weight/distance is lower and put back 
	 * into the heap. 
	 * 		Label the node as known.  
	 * 4.) Pull out the next lowest label and proceed until the user supplied 
	 * destination node is found and ends the search for the 
			shortest path and distance/weight of trip.
	 * @param the_graph, a SimpleGraph converted from a list of vertexes with 
	 * an edge weight associated with each
	 * @param the_source, a vertex to start the traversal from
	 * @param the_dest, a vertex to end the traversal
	 */
	@SuppressWarnings("unchecked")
	public ShortestPath(SimpleGraph the_graph, Vertex the_source, 
			Vertex the_dest){
		//Initialize the heap in order to store the DijkstraNodes and make it 
		//faster for choosing which one has the lowest label.  
		BinaryHeap heap = new BinaryHeap();  
		
		//Create an iterator to travel over each of the graphs vertices.
		Iterator<Vertex> it = the_graph.vertices();  
		
		//Iterate over the vertices and create corresponding DijkstraNodes.
		//When we find the source vertex we make sure to set its label to 0 and immediately add it to he known set.
		while(it.hasNext()){
			//Get the first vertex and call it temp
			Vertex temp_v = it.next();			
			//Create a DijkstraNode and pass a pointer to the temp vertex
			DijkstraNode temp_d = new DijkstraNode(temp_v);	
			//Provide a pointer to the DNode to the Vertex (Doubly Linked)
			temp_v.setData(temp_d);	
			//Wait until the user supplied source is found and add to known 
			//set with a label weight of 0.
			if(temp_v == the_source){						 
				temp_d.setLabel(0.0);
				temp_d.setKnown(true);
			}
			
			//System.out.println("Inserted " +temp_d.getVertexPtr().getName()+" 
			//into the heap, with label " + temp_d.getLabel());
			
			//Insert our newly created DijkstraNode into the heap.
			heap.insert(temp_d);  //Add the vertex to the heap.
		}
		
		DijkstraNode end = null;
		
		//Pull out the next vertex with the smallest label (the start will always be the first
		//becuase it is set to 0 and the rest are set to max).
		//Add it to the known set
		//Then iterate over it's adjacent vertices that are not in the known set
		//and try to update their label with a lower value if possible.
		while(!heap.isEmpty()){
			
			DijkstraNode node = null;
			try {
				//Get the next vertex with the smallest label and add it to the known set.
				node = heap.deleteMin();
				node.setKnown(true);
				//System.out.println("Popped " +node.getVertexPtr().getName()+
				//"off the heap, with label " + node.getLabel());
				
				//Did we just add our destination to the known set? then STOP!
				if(node.getVertexPtr() == the_dest){
					end = node;
					break;
				}
			} catch (EmptyHeapException e) {
				//There should be no way to reach this statement because we check for empty just before the delete.
				e.printStackTrace();
			}
			
			Iterator<Edge> edges = the_graph.incidentEdges(node.getVertexPtr());
			//Iterate over the adjacent edges.
			while(edges.hasNext()){
				//Grab the first and/or next edge connecting from the known 
				//vertex
				Edge temp = edges.next();				
				//Store the value of the weight from the known vertex. 
				Double weight = (Double)temp.getData();  
				//Grab the resulting Dijstra node refered to by the known 
				//vertex's edge reference.
				DijkstraNode other = 
					(DijkstraNode) the_graph.opposite(
							node.getVertexPtr(), temp).getData();  
				
				//If the opposite node is not in the known set then, 
				//compare the weights of the current label vs. the possibly new 
				//replacement weight.  Relabel if lower.  Add the Node back in
				//and percolate up the heap.  
				if(!other.getKnown() && other.getLabel() > weight + node.getLabel()){
					other.setLabel(weight + node.getLabel());
					//System.out.println("Set vertex "+ 
					//(String)other.getVertexPtr().getName() + " label to " + 
					//(weight + node.getLabel()));
					
					//Because the label changed we now have to call percolateUp on the node so that it
					//can get to its proper place in the heap.
					heap.percolateUp(other.getHeapLocation());
					//Tell it where the shortest path came from so we can backtrack later.
					other.setPreviousNodePtr(node);
				}
			}
		}
		
		//Get the final distance from the destination node (this is the distance of the shortest path)
		distance = end.getLabel();  								
		//Init a linked list to add the traversal path too. 
		//(End to Start)(Reverse)
		LinkedList<Vertex> reverse_path = new LinkedList<Vertex>();	
		//Add the end vertex to the linked list.
		reverse_path.add(end.getVertexPtr());						
		
		DijkstraNode current = end;
		
		//Look at the pointer of end nodes node and add to list.  Repeat.
		while(current.getPreviousNodePtr() != null){
			reverse_path.add(current.getPreviousNodePtr().getVertexPtr());
			current = current.getPreviousNodePtr();
		}
		
		path = new LinkedList<Vertex>();
		
		//Re order the path from start to end.  
		Object[] reverse_path_array = reverse_path.toArray();
		for(int i = reverse_path_array.length -1;i >= 0;i--){
			path.add((Vertex)reverse_path_array[i]);
		}
		
	}
	
	/**
	 * Supply the distance between the start vertex and the destination vertex 
	 * of the SimpleGraph that was supplied to the ShortestPath Method. 
	 * @return the distance between the start vertex and the destination vertex
	 */
	public Double getDistance() {
		return distance;
	}
	
	/**
	 * Supply the path between the start vertex and the destination vertex of 
	 * the SimpleGraph
	 * that was supplied to the ShortestPath Method. 
	 * @return the path between the start vertex and the destination vertex
	 */
	public LinkedList<Vertex> getPath(){
		return path;
	}
	
}
